﻿/*	
	stencil - action script 3 isometric game engine.

	http://code.google.com/p/stencilas3/
	
	Copyright (c) 2010 Max Zhuravkov, All Rights Reserved.

	Permission is hereby granted, free of charge, to any person obtaining a copy of
	this software and associated documentation files (the "Software"), to deal in
	the Software without restriction, including without limitation the rights to
	use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
	of the Software, and to permit persons to whom the Software is furnished to do
	so, subject to the following conditions:

	The above copyright notice and this permission notice shall be included in all
	copies or substantial portions of the Software.

	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
	SOFTWARE.
*/
package stencil.core.engine.utils 
{
	import flash.geom.Point;
	import flash.geom.Rectangle;
	import stencil.core.engine.Position;
	
	/**
	 * 
	 * @author Max Zhuravkov
	 */
	public final  class MathUtil {
		
		/**
		 * Calculates manhatten distance between two points.
		 * @param	p1	the first point.
		 * @param	p2	the second point.
		 * @return
		 */
		public static function manhattenDistance(p1:Point, p2:Point):Number {
			return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
		}
		
		/**
		 * Calculates manhatten distance between two points.
		 * @param	p1	the first point.
		 * @param	p2	the second point.
		 * @return
		 */
		public static function manhattenDistanceBetweenPositions(p1:Position, p2:Position):Number {
			
			return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y) + Math.abs(p1.z - p2.z);
		}
		
		/**
		 * Calculates euclidian distance between two points.
		 * @param	p1	the first point.
		 * @param	p2	the second point.
		 * @return
		 */
		public static function euclidianDistance(p1:Point, p2:Point):Number {
			var dx:Number = p1.x - p2.x;
			var dy:Number = p1.y - p2.y;
			
			return Math.sqrt(dx * dx + dy * dy);
		}
		
		/**
		 * Calculates euclidian distance between two points.
		 * @param	p1	the first point.
		 * @param	p2	the second point.
		 * @return
		 */
		public static function euclidianDistanceBetweenPositions(p1:Position, p2:Position):Number {
			var dx:Number = p1.x - p2.x;
			var dy:Number = p1.y - p2.y;
			var dz:Number = p1.z - p2.z;
			
			return Math.sqrt(dx*dx + dy*dy + dz*dz);
		}
		
		/**
		 * Calculates the distance from the point to the line segment.
		 * 
		 * @param	p
		 * @param	a
		 * @param	b
		 * 
		 * @return
		 */
		public static function distanceToLine(p:Point, a:Point, b:Point):Number {
			var dx:Number = a.x - b.x;
			var dy:Number = a.y - b.y;
			
			return (p.x*(a.y - b.y) + p.y*(b.x - a.x) + a.x*b.y - b.x*a.y)/Math.sqrt(dx*dx + dy*dy)
		}
		
		/**
		 * Calculates the distance from the point to the line segment.
		 * 
		 * @param	p
		 * @param	a
		 * @param	b
		 * 
		 * @return
		 */
		public static function absDistanceToLine(p:Point, a:Point, b:Point):Number {
			return Math.abs(distanceToLine(p, a, b));
		}
		
		
		/**
		 * Calculates an intersection between two line segments.
		 * 
		 * @param	a1	the first end point of the first line segment.
		 * @param	b1	the second end point of the first line segment.
		 * @param	a2	the first end point of the second line segment.
		 * @param	b2	the second end point of the second line segment.
		 * 
		 * @return
		 */
		public static function lineSegment2lineSegmentIntersection(a1:Point, b1:Point, a2:Point, b2:Point):Point {
			
			if (a1.equals(a2) || a1.equals(b2))
			{
				return a1.clone();
			}
			
			if (b1.equals(a2) || b1.equals(b2))
			{
				return b1.clone();
			}
			
			var x1:Number = a1.x;
			var y1:Number = a1.y;
			var x2:Number = b1.x;
			var y2:Number = b1.y;
			
			var x3:Number = a2.x;
			var y3:Number = a2.y;
			var x4:Number = b2.x;
			var y4:Number = b2.y;
			
			var UBottom:Number = ((y4-y3)*(x2-x1))-((x4-x3)*(y2-y1));
			if (UBottom != 0) {
				var Ua:Number = (((x4-x3)*(y1-y3))-((y4-y3)*(x1-x3)))/UBottom;
				var Ub:Number = (((x2-x1)*(y1-y3))-((y2-y1)*(x1-x3)))/UBottom;
				if ((Ua>=0) && (Ua<=1) && (Ub>=0) && (Ub<=1)) {
					var i:Point = new Point();
					i.x = x1+(Ua*(x2-x1));
					i.y = y1+(Ua*(y2-y1));
					return i;
				}
			}
			return null;
			
		}
		
		
		
		/**
		 * Determines whether polygon represented by the array of its vertices contains the given point or not.
		 * 
		 * @param	p
		 * @param	points
		 * 
		 * @return
		 */
		public static function polyContains(p:Point, points:Array):Boolean {
			var c:Boolean = false;
			var x:Number = p.x;
			var y:Number = p.y;
			var length:Number = points.length;
			var j:int =  length - 1;
			for (var i:int = 0; i < length; j = i++) {
				var pi:Point = points[i];
				var pj:Point = points[j];
				
				if (p.equals(pi) || p.equals(pj)) {
					return true;
				}
				
				if ((((pi.y <= y) && (y < pj.y)) || ((pj.y <= y) && (y < pi.y))) 
					 && (x > (pj.x - pi.x) * (y - pi.y) / (pj.y - pi.y) + pi.x)){
					c = !c;
				}
			}
			return c;
		}
		
		/**
		 * Calculates intersection between the rectangle and the convex polygon.
		 * 
		 * @param	rect	the rectanle
		 * @param	poly	the array of polygon vertices.
		 * 
		 * @return
		 */
		public static function rect2PolyIntercection(rect:Rectangle, poly:Array):Array {
			
			var results:Array = [];
			var length:int = poly.length;
			var rectPoints:Array = [rect.topLeft, new Point(rect.right, rect.top), rect.bottomRight, new Point(rect.left, rect.bottom)];
			
			for (var i:int = 0; i < length; i ++) {
				var prev:Point = i - 1 >= 0 ? poly[i - 1] : poly[length - 1];
				var p:Point = poly[i];
				var next:Point = i + 1 >= length ? poly[0] : poly[i + 1];
				
				var ip0:Point = line2RectIntersection(p, prev, p, rectPoints, results);
				var ip1:Point = line2RectIntersection(p, p, next, rectPoints, results);
				var inside:Boolean = rect.containsPoint(p);
				var nearest:Point = null;
				
				if (ip0) {
					addPointToArray(ip0, results)
				}
				
				if (inside) {
					addPointToArray(p, results)
				}else {
					
					nearest = findNearestPoint(p, rectPoints).shift();
						
					if (polyContains(nearest, poly)) {
						addPointToArray(nearest, results)
					}
				}
				
				if (ip1) {
					addPointToArray(ip1, results)
				}
			}
			
			return results;
		}
		
		/**
		 * Returns the nearest point to the given one.
		 * 
		 * @param	p		the point.
		 * @param	points	
		 * 
		 * @return
		 */
		public static function findNearestPoint(p:Point, points:Array):Array {
			var sorted:Array = points.concat();
			var length:int = sorted.length;
			
			sortPoints(p, sorted);
				
			return sorted;
		}
		
		
		/**
		 * Sorts array of points.
		 * 
		 * @param	p
		 * @param	points
		 */
		public static function sortPoints(p:Point, points:Array):void {
			var length:int = points.length;
			
			for (var i:int = 0; i < length; i ++  ) {
				var swapped:Boolean = false;
				for (var j:int = 0; j < length - i - 1; j ++ ) {
					var a:Point = points[j];
					var dx:Number = p.x - a.x
					var dy:Number = p.y - a.y;
					var d:Number = Math.sqrt(dx * dx + dy * dy);
					var b:Point = points[j + 1];
					dx = p.x - b.x
					dy = p.y - b.y;
					var d2:Number = Math.sqrt(dx * dx + dy * dy);
					
					if (d > d2) {
						points[j] = b;
						points[j + 1] = a;
						swapped = true;
					}
					
				}
				if (!swapped) {
					break;
				}
			}
		}
		
		private static function addPointToArray(p:Point, array:Array):void {
			var found:Boolean = false;
			
			if (array.length) {
				for each(var p1:Point in array) {
					if (p1.equals(p)) {
						found = true;
						break;
					}
				}
			}
			
			if (!found) {
				array.push(p);
			}
		}
		
		private static function line2RectIntersection(p:Point, a:Point, b:Point, points:Array, out:Array):Point {
			var length:int = points.length;
			var intersection:Point = null;
			var lowest:Number = Number.MAX_VALUE;
			
			for (var i:int = 0; i < length; i ++ ) {
				var p0:Point = points[i];
				var p1:Point = points[(i + 1 < length ? i + 1 : 0)];
				var ip:Point = MathUtil.lineSegment2lineSegmentIntersection(a, b, p0, p1);
				
				if (!ip) {
					continue;
				}
				
				var d:Number = MathUtil.euclidianDistance(p, ip);
				
				if (d < lowest) {
					intersection = ip;
					lowest = d;
				}
			}
			
			return intersection;
		}
	}
}
